10245. Имена и
буквы
Заданы имена n людей (пронумерованных от 1 до n в заданном порядке), где
каждое имя написано в отдельной строке.
Ваша задача – ответить на m запросов вида “A B”, где A соответствует
номеру человека, а B – индексу буквы в имени человека.
Для каждого запроса выведите
один соответствующий символ в имени человека.
Вход. Первая строка содержит
количество людей n (n ≤ 105) и число запросов m (m ≤ 1000). Каждая из следующих n строк содержит одно имя и может быть
до 105 символов.
Каждая из следующих m строк содержит два целых числа A (1 ≤ A ≤ n) и B (0 ≤ B < длина имени человека номер A).
Известно, что входные данные
содержат не более 106 символов.
Выход.
Для каждого запроса “A B” выведите символ номер B в имени человека номер A. Все
символы следует выводить в одной строке.
|
Пример входа |
Пример выхода |
|
|
3 5 Alice Bob John 1 3 2 1 3 2 3 3 1 0 |
cohnA |
|
динамический
массив
Занесем имена людей в
динамический массив. Затем ответим на запросы.
Реализация алгоритма
Объявим массив
указателей names
для хранения имен.
Объявим дополнительно символьный массив s.
#define SIZE 100005
char *names[SIZE];
char s[SIZE];
Читаем количество
людей n и число запросов m.
scanf("%d
%d", &n, &m);
for (i = 0; i <
n; i++)
{
Читаем имя человека s и вычисляем его длину len.
scanf("%s", s);
int len = strlen(s) + 1;
Выделяем память под имя человека. Копируем имя из строки s.
names[i]
= (char *)malloc(len);
strncpy(names[i],
s, len);
}
Обрабатываем m запросов.
for (i = 0; i <
m; i++)
{
Читаем значения a и b. Выводим символ номер B в имени
человека номер A.
scanf("%d %d", &a,
&b);
putchar(names[a
- 1][b]);
}
Реализация алгоритма – stl
#include <iostream>
#include <string>
#include <vector>
using namespace std;
int i, j, n, m, a,
b;
vector<string> s;
string q;
int main(void)
{
cin
>> n >> m;
s.push_back("");
for (i = 0; i < n; i++)
{
cin >> q;
s.push_back(q);
}
for (i = 0; i < m; i++)
{
cin >> a >> b;
printf("%c", s[a][b]);
}
printf("\n");
return 0;
}